package a.codetop.笔试框架.天王;

import java.util.*;

public class 凑和模板 {

    //—————————————————————————————————————————————————————————————————————————————————————————————————————————————
    //暴力拿具体List
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    //Arrays.sort(nums); //先sort！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

    public void 每样一个凑和_所有路径的List集合(int[] nums,int tS,int ci) {
        //先Arrays.sort(nums)//先sort！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
        if(ci==nums.length)return;
        for(int i=ci;i<nums.length;i++){
            tmp.add(nums[i]);
            if(tS-nums[i]==0)res.add(new ArrayList<>(tmp));
            //
            每样一个凑和_所有路径的List集合(nums,tS-nums[i],i+1);
            //
            tmp.remove(tmp.size()-1);
        }
    }
    public void 每样无限凑和_所有路径的List集合(int[] nums,int tS,int fi) {
        //先Arrays.sort(nums)//先sort！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
        if(tS<=0){
            if(tS==0)res.add(new ArrayList<>(tmp));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(i<fi)continue;
            tmp.add(nums[i]);
            //
            每样无限凑和_所有路径的List集合(nums,tS-nums[i],i);
            //
            tmp.remove(tmp.size()-1);
        }
    }
    //万能↑————————————————————————————————————————————————————————————————————————————————————————————————————————


    //DP↓—————————————————————————————————————————————————————————————————————————————————————————————————————————
    //每样一个凑和
    public int 每样一个凑和_所有路径总数(int[] nums, int tS){
        int n=nums.length;
        int[][] dp=new int[n+1][tS+1];
        //
        //1、叶子节点找到tS=0:return1
        //2、没找到return0
        for(int i=0;i<dp.length;i++){
            dp[i][0]=1;
        }
        //
        for(int i=1;i<=n;i++){
            int val=nums[i-1];
            for(int j=0;j<=tS;j++){
                //不够拿：不拿
                if(val>j)  dp[i][j]=dp[i-1][j];
                    //够拿：不拿+拿
                else       dp[i][j]=dp[i-1][j]+dp[i-1][j-val];
            }
        }
        //
        return dp[n][tS];//0没找到
    }
    //每样无限凑和
    public int 每样无限凑和_所有路径总数(int[] nums, int tS){
        int n=nums.length;
        int[][] dp=new int[n+1][tS+1];
        //
        //1、叶子节点找到tS=0:return1
        //2、没找到return0
        for(int i=0;i<dp.length;i++)
            dp[i][0]=1;
        //
        for(int i=1;i<=n;i++){
            int val=nums[i-1];
            for(int j=1;j<=tS;j++){//j=1起,跳过上面初始化的j=0
                for(int k=0;k*val<=j;k++){
                    dp[i][j]+=dp[i-1][j-k*val];
                }
            }
        }
        //
        return dp[n][tS]==9999?-1:dp[n][tS];//-1没找到
    }
    public int 每样无限凑和_最少币个(int[] nums, int tS){
        int n=nums.length;
        int[][] dp=new int[n+1][tS+1];
        //
        //1、叶子节点没找到正好凑tS的：求min要用9999排除干扰
        //2、叶子节点找到tS=0的：return0,因为上面每轮有+个数k
        for(int i=0;i<dp.length;i++)
            for(int j=0;j<dp[0].length;j++)
                dp[i][j]=9999;
        dp[0][0]=0;//00算一种可能,被9999覆盖了,改回0
        //
        for(int i=1;i<=n;i++){
            int val=nums[i-1];
            for(int j=0;j<=tS;j++){
                for(int k=0;k*val<=j;k++){
                    dp[i][j]=Math.min(
                            dp[i][j],
                            dp[i-1][j-k*val]+k
                    );
                }
            }
        }
        //
        return dp[n][tS]==9999?-1:dp[n][tS];//-1没找到
    }
    //—————————————————————————————————————————————————————————————————————————————————————————————————————————————



}
